//给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 
//
// 示例 1： 
//
// 输入: "babad"
//输出: "bab"
//注意: "aba" 也是一个有效答案。
// 
//
// 示例 2： 
//
// 输入: "cbbd"
//输出: "bb"
// 
// Related Topics 字符串 动态规划


package leetcode.d_1_99;

//Java：最长回文子串
public class P5LongestPalindromicSubstring{
    public static void main(String[] args) {
        Solution solution = new P5LongestPalindromicSubstring().new Solution();
        System.out.println(solution.longestPalindrome("ac"));
        System.out.println(solution.longestPalindrome("ccc"));
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    //暴力求解
//    class Solution {
//        public String longestPalindrome(String s) {
//            int len = s.length();
//            if (len < 2){
//                return s;
//            }
//
//            int maxLen = 1;
//            int begin = 0;
//
//            char[] chars = s.toCharArray();
//            for (int i = 0; i < len -1; i++) {
//                for (int j = i+1; j < len; j++) {
//                    if (j - i + 1 > maxLen && valid(chars, i, j)){
//                        maxLen = j - i + 1;
//                        begin = i;
//                    }
//                }
//            }
//            return s.substring(begin, begin + maxLen);
//        }
//
//        private boolean valid(char[] chars, int i, int j) {
//            while (i < j){
//                if (chars[i] != chars[j]){
//                    return false;
//                }
//                i++;
//                j--;
//            }
//            return true;
//        }
//    }

    //DP
    class Solution {
        public String longestPalindrome(String s) {
            int len = s.length();
            if (len < 2){
                return s;
            }

            int maxLen = 1;
            int begin = 0;

            // dp[i][j] 表示 s[i, j] 是否是回文串
            boolean[][] dp = new boolean[len][len];
            char[] charArray = s.toCharArray();

            for (int i = 0; i < len; i++) {
                dp[i][i] = true;
            }

            for (int j = 1; j < len; j++) {
                for (int i = 0; i < j; i++) {
                    if (charArray[i] != charArray[j]){
                        dp[i][j] = false;
                    }else {
                        if (j - i < 3){
                            dp[i][j] = true;
                        }else {
                            dp[i][j] = dp[i+1][j-1];
                        }
                    }

                    if (dp[i][j] && j-i+1 > maxLen){
                        maxLen = j - i + 1;
                        begin = i;
                    }
                }
            }
            return s.substring(begin, begin + maxLen);
        }
    }

    //解法有问题 "abcda" 有问题
//    class Solution {
//        public String longestPalindrome(String s) {
//            int len = s.length();
//            if (len < 2){
//                return s;
//            }
//            int[][] dp = new int[len][len];
//            for (int i = 0; i < len; i++) {
//                dp[i][i] = 1;
//            }
//            int maxLen = 1;
//            int left = 0;
//            for (int j = 1; j < len; j++) {
//                for (int i = 0; i < j; i++) {
//                    if (s.charAt(i) == s.charAt(j)){
//                        dp[i][j] = dp[i+1][j-1] + 2;
//                        if (dp[i][j] > maxLen){
//                            maxLen = dp[i][j];
//                            left = i;
//                        }
//                    }
//                }
//            }
//            return s.substring(left, left+maxLen);
//        }
//
//    }
//leetcode submit region end(Prohibit modification and deletion)

}